/*
 * @lc app=leetcode.cn id=110 lang=cpp
 *
 * [110] 平衡二叉树
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
//一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，
//因此可以使用递归的方式判断二叉树是不是平衡二叉树
//自顶向下调用
    int judge(TreeNode* root) {
        if(!root) {
            return 0;
        }
        return max(judge(root->left),judge(root->right)) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) {
            return true;
        }
        //判断其左子树的平衡因子与右子树的平衡因子之差小于1 并且递归判断左子树和右子树
        return abs(judge(root->left) - judge(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};
// @lc code=end

